package com.ccsoft.leetcode.service;

import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.List;

/**
 * 2021年11月18日 14:04:20 chanchaw
 * 94. 二叉树中序遍历
 */
@Service
public class TraversalTree {
    public void traversal(){
        TreeNode root = buildTreeNode();
//        List<TreeNode> list = new ArrayList<>();
//        ergodic(root,list);
//        System.out.println(list);

        // 中序遍历 - 已测试通过，正确结果：4251637
//        List<Integer> list1 = new ArrayList<>();
//        ergodicMid(root,list1);
//        System.out.println(list1);

        // 前序（先序）遍历，正确结果：1245367
//        List<Integer> list1 = new ArrayList<>();
//        ergodicFirst(root,list1);
//        System.out.println(list1);

        // 后序遍历 - 正确结果：4526731
        List<Integer> list1 = new ArrayList<>();
        ergodicBack(root,list1);
        System.out.println(list1);
    }

    public void ergodic(TreeNode node, List<TreeNode> list){
        if( node.left != null ) ergodic(node.left,list);
        list.add(node);
        if( node.right != null ) list.add(node.right);
    }

    /**
     * 后序遍历 - 正确结果：4526731
     * 将二叉树填充到集合的顺序：左，右，根
     * @param node
     * @param list
     */
    public void ergodicBack(TreeNode node, List<Integer> list){
        if( node.left != null ) ergodicBack(node.left,list);
        if( node.right != null ) ergodicBack(node.right,list);
        list.add(node.val);
    }

    /**
     * 二叉树先序遍历，正确结果：1245367
     * 将二叉树填充到集合的顺序：根，左，右
     * @param node
     * @param list
     */
    public void ergodicFirst(TreeNode node, List<Integer> list){
        list.add(node.val);
        if( node.left != null ) ergodicFirst(node.left,list);
        if( node.right != null ) ergodicFirst(node.right,list);
    }

    /**
     * 二叉树中序遍历，正确结果：4251637
     * 将二叉树填充到集合的顺序：左，根，右
     * @param node
     * @param list
     */
    public void ergodicMid(TreeNode node, List<Integer> list){
        if( node.left != null ) ergodicMid(node.left,list);
        list.add(node.val);
        if( node.right != null ) ergodicMid(node.right,list);
    }

    public TreeNode buildTreeNode(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node1.left = node2;
        node1.right = node3;

        return node1;
    }

    public class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}


